package 题目集.线段树or树状数组.线段树;

import org.junit.Test;

import java.util.Arrays;

/**
 * 对数器验证
 */
public class ch02_重置模板_懒标记 {

    static Node[] tree;
    static long[] src;
    static int n, tn;

    //相当于main方法，这个方法仅仅是为了测试
    public static void init(long[] arr) {
        src = arr;
        n = arr.length - 1;
        tn = (int) Math.pow(2, Math.ceil(Math.log(n) / Math.log(2)) + 1);
        tree = new Node[tn];
        build(1, 1, n);
    }

    public static void build(int i, int l, int r) {
        tree[i] = new Node(l, r);
        if (l == r) {
            tree[i].val = src[l];
            return;
        }
        int m = l + r >> 1;
        build(i << 1, l, m);
        build(i << 1 | 1, m + 1, r);
        pull(i);
    }

    public static void update(int i, int l, int r, long v) {
        if (l <= tree[i].l && tree[i].r <= r) {
            updateLazy(i,v);
            return;
        }
        push(i);
        int m = tree[i].l + tree[i].r >> 1;
        if (l <= m) {
            update(i << 1, l, r, v);
        }
        if (m < r) {
            update(i << 1 | 1, l, r, v);
        }
        pull(i);
    }

    public static long query(int i, int l, int r) {
        if (l <= tree[i].l && tree[i].r <= r) {
            return tree[i].val;
        }
        push(i);
        long res = 0;
        int m = tree[i].l + tree[i].r >> 1;
        if (l <= m) {
            res += query(i << 1, l, r);
        }
        if (m < r) {
            res += query(i << 1 | 1, l, r);
        }
        return res;
    }

    public static void push(int i) {
        if (tree[i].tag) {
            updateLazy(i << 1, tree[i].updateVal);
            updateLazy(i << 1 | 1, tree[i].updateVal);
            tree[i].tag = false;
            tree[i].updateVal = 0;
        }
    }

    public static void updateLazy(int i, long v) {
        tree[i].val = tree[i].len * v;
        tree[i].updateVal = v;
        tree[i].tag = true;
    }

    public static void pull(int i) {
        tree[i].val = tree[i << 1].val + tree[i << 1 | 1].val;
    }


    static class Node {
        int l, r, len;
        long val;
        long updateVal;
        boolean tag;   //存在任务的标记

        public Node(int l, int r) {
            this.l = l;
            this.r = r;
            len = r - l + 1;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "l=" + l +
                    ", r=" + r +
                    ", len=" + len +
                    ", val=" + val +
                    ", updateVal=" + updateVal +
                    ", flag=" + tag +
                    '}';
        }
    }

    //以下是测试
    @Test
    public void test() {
        long[] arr = {0, 0, 0, 0, 3, 3};
        init(arr);
        update(1, 1, 5, 1);
        long query = query(1, 1, 4);
        System.out.println(query);
    }

    static int MAXN = 10000;

    static long[] origin = new long[MAXN + 1];

    public static void main(String[] args) {
        int cnt = 200;
        System.out.println("测试开始");
        while (cnt-- > 0) {
            compare();
        }
        System.out.println("测试结束");
    }

    public static void compare() {
        int v = 10000;
        int t = 10000;
        // 生成随机值填入arr数组
        randomArray(MAXN, v);
        // 建立线段树
        init(origin.clone());
        long[] arr = origin;
//        build(1, n, 1);
        // 生成验证的结构
        long[] check = origin.clone();
        long[][] ops = new long[t][4];
        for (int i = 0; i < t; i++) {
            // 生成操作类型
            // op = 0 更新操作
            // op = 1 查询操作
            ops[i][0] = (int) (Math.random() * 2);
            // 下标从1开始，不从0开始，生成两个随机下标
            int a = (int) (Math.random() * MAXN) + 1;
            int b = (int) (Math.random() * MAXN) + 1;
            // 确保jobl <= jobr
            int jobl = Math.min(a, b);
            int jobr = Math.max(a, b);
            ops[i][1] = jobl;
            ops[i][2] = jobr;
            if (ops[i][0] == 0) {
                // 更新操作
                // 线段树、验证结构同步更新
                int jobv = (int) (Math.random() * v * 2) - v;
                ops[i][3] = jobv;
                update(1, jobl, jobr, jobv);
                checkUpdate(check, jobl, jobr, jobv);
            } else {
                // 查询操作
                // 线段树、验证结构同步查询
                // 比对答案
                long ans1 = query(1, jobl, jobr);
                long ans2 = checkQuery(check, jobl, jobr);
                if (ans1 != ans2) {
                    System.out.println("出错了!\t ans=" + ans2 + "\terror=" + ans1);
                    for (long[] op : ops) {
                        System.out.println(Arrays.toString(op));
                    }
                }
            }
        }
    }

    // 生成随机值填入arr数组
    // 为了验证
    public static void randomArray(int n, int v) {
        for (int i = 1; i <= n; i++) {
            origin[i] = (long) (Math.random() * v);
        }
    }

    // 验证结构的更新
    // 暴力更新
    // 为了验证
    public static void checkUpdate(long[] check, int jobl, int jobr, long jobv) {
        for (int i = jobl; i <= jobr; i++) {
            check[i] = jobv;
        }
    }

    // 验证结构的查询
    // 暴力查询
    // 为了验证
    public static long checkQuery(long[] check, int jobl, int jobr) {
        long ans = 0;
        for (int i = jobl; i <= jobr; i++) {
            ans += check[i];
        }
        return ans;
    }

}
